package algorithm.leetcode.I101to200;

import algorithm.leetcode.TreeNode;

public class Q124 {

    int maxRoute = 0;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxRoute;
    }

    /**
     * 计算每个节点作为根节点时,向其左右子树中找一条路径使得路径上的和最大(注意这条路径一定包含根节点,但不一定要到叶子节点)
     * @param node 待计算的节点,作为根节点
     * @return 以根节点为顶端的一条最大路径
     */
    private int maxGain(TreeNode node) {
        if (node == null) return 0;

        int leftGain = maxGain(node.left);
        int rightGain = maxGain(node.right);
        // 以根节点为顶端的一条最大路径,可能是根+左子,或根+右子,或者只有根
        int gain = Math.max(Math.max(leftGain, rightGain), 0);
        maxRoute = Math.max(Math.max(maxRoute, leftGain+rightGain+node.val), gain+node.val);
        return gain + node.val;
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(2);
        TreeNode treeNode2 = new TreeNode(-2);
        TreeNode treeNode3 = new TreeNode(3);
        treeNode1.left = treeNode2;
        // treeNode1.right = treeNode3;
        Q124 q124 = new Q124();
        System.out.println(q124.maxPathSum(treeNode1));
    }
}
